﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DXBase.Structs
{
	public interface IBounds
	{
		/// <summary>
		/// Return whether this box wholly Contains the argument box
		/// </summary>
		bool Contains(IBounds b);
		/// <summary>
		/// Return whether this box Intersects the argument box
		/// </summary>
		bool Intersects(IBounds b);
		/// <summary>
		/// The size of the box along the longest axis
		/// </summary>
		float MaxLength { get; }
	}
	public interface IHasBounds<T>
		where T: IBounds
	{
		T Bounds { get; }
	}

	/// <summary>
	/// A (spatial) binary search tree for object with a Bounds
	/// </summary>
	public abstract class SpatialIndex<TItem, TBounds> : ICollection<TItem>, IHasBounds<TBounds>
		where TItem: IHasBounds<TBounds>
		where TBounds: IBounds
	{
		Node root;
		float min;

		public SpatialIndex(TBounds bounds, int maxDepth = 20)
		{
			if (maxDepth < 1 || maxDepth > 30)
				throw new ArgumentOutOfRangeException("maxDepth", "maxDepth should be in interval [1, 30]");
			root = new Node(bounds);
			min = root.Bounds.MaxLength / (1 << maxDepth);
		}
		public SpatialIndex(TBounds bounds, float res)
		{
			if (res <= float.Epsilon)
				throw new ArgumentOutOfRangeException();
			root = new Node(bounds);
			min = res;
		}

		public TBounds Bounds { get { return root.Bounds; } }
		public float Resolution { get { return min; } }

		#region Node

		public class Node : IHasBounds<TBounds>
		{
			TBounds bounds;
			Node[] children;

			List<TItem> elements = new List<TItem>();

			public Node(TBounds bounds)
			{
				this.bounds = bounds;
			}
			public TBounds Bounds { get { return bounds; } }

			public int Count
			{
				get
				{
					int res = elements.Count;
					if(children != null)
						foreach (var item in children)
							res += item.Count;
					return res;
				}
			}

			public void Add(SpatialIndex<TItem, TBounds> tree, TItem obj, TBounds bounds)
			{
				if (children == null && this.bounds.MaxLength > tree.Resolution)
				{
					var rSubBounds = tree.Divide(bounds);
					children = new Node[rSubBounds.Count];
					for (int i = 0; i < children.Length; i++)
						children[i] = new Node(rSubBounds[i]);
				}

				if (children != null)
					for (int i = 0; i < children.Length; i++)
						if (children[i].Bounds.Contains(bounds))
						{
							children[i].Add(tree, obj, bounds);
							return;
						}

				elements.Add(obj);
			}

			public bool Remove(TItem obj, TBounds r)
			{
				if (obj == null)
					throw new ArgumentNullException();

				if (children != null)
					for (int i = 0; i < children.Length; i++)
						if (children[i].Bounds.Contains(r))
							return children[i].Remove(obj, r);

				return elements.Remove(obj);
			}

			public void Updated(SpatialIndex<TItem, TBounds> tree, TItem obj, TBounds old, TBounds bounds)
			{
				if (children != null)
					for (int i = 0; i < children.Length; i++)
						if (children[i].Bounds.Contains(bounds) && children[i].Bounds.Contains(old))
						{
							children[i].Updated(tree, obj, old, bounds);
							return;
						}

				Remove(obj, old);
				Add(tree, obj, bounds);
			}

			public IEnumerable<TItem> Query(TBounds sr)
			{
				foreach (Node n in QueryNode(sr))
					foreach (var item in n.elements)
						if (sr.Intersects(item.Bounds))
							yield return item;
			}

			public IEnumerable<Node> QueryNode(TBounds r)
			{
				if (children != null)
				{
					foreach (var c in children)
					{
						if (c.Bounds.Intersects(r))
						{
							foreach (var item in c.QueryNode(r))
								yield return item;
						}
					}
				}
				yield return this;
			}

			public IEnumerable<TItem> Query(Predicate<TBounds> intersects)
			{
				foreach (Node n in QueryNode(intersects))
					foreach (var item in n.elements)
						if (intersects(item.Bounds))
							yield return item;
			}

			public IEnumerable<Node> QueryNode(Predicate<TBounds> intersects)
			{
				if (children != null)
				{
					foreach (var c in children)
					{
						if (intersects(c.Bounds))
						{
							foreach (var item in c.QueryNode(intersects))
								yield return item;
						}
					}
				}
				yield return this;
			}

			public void Clear()
			{
				if (children != null)
					foreach (var c in children)
						c.Clear();
				elements.Clear();
			}
		}

		#endregion

		public IEnumerable<TItem> Query(TBounds r) { return root.Query(r); }
		public IEnumerable<TItem> Query(Predicate<TBounds> intersects) { return root.Query(intersects); }

		public void Updated(TItem item, TBounds old)
		{
			if (item != null)
				root.Updated(this, item, old, item.Bounds);
		}

		/// <summary>
		/// Partition the space by splitting a big box in smaller box (which still totally fill the big box)
		/// </summary>
		public abstract IList<TBounds> Divide(TBounds bounds);

		#region ICollection<T>

		public void Add(TItem b) 
		{
			if (b != null)
				root.Add(this, b, b.Bounds);
		}

		public bool Remove(TItem b) { return b != null ? root.Remove(b, b.Bounds) : false; }

		public void Clear() { root.Clear(); }

		public bool Contains(TItem item)
		{
			foreach (var candidate in Query(item.Bounds))
				if (Equals(candidate, item))
					return true;
			return false;
		}

		public void CopyTo(TItem[] array, int arrayIndex)
		{
			var all = Query(root.Bounds).ToArray();
			all.CopyTo(array, arrayIndex);
		}

		public int Count { get { return root.Count; } }

		public bool IsReadOnly { get { return false; } }

		public IEnumerator<TItem> GetEnumerator() 
		{
			foreach (var item in Query(root.Bounds))
				yield return item;
		}

		System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return GetEnumerator(); }

		#endregion
	}
}
